import time
from gen import generate_test_data
from alg import Solution

def test_algorithm():
    """测试回溯算法正确性"""
    test_cases = generate_test_data()
    
    print("=== 目标和问题测试（回溯算法）===")
    print("使用回溯算法求解\n")
    
    for i, (nums, target) in enumerate(test_cases, 1):
        print(f"测试用例 {i}:")
        print(f"输入: nums = {nums}, target = {target}")
        
        # 只对小规模数据进行测试，避免超时
        if len(nums) <= 15:
            solution = Solution()
            start_time = time.time()
            result = solution.findTargetSumWays(nums, target)
            elapsed_time = time.time() - start_time
            
            print(f"回溯算法结果: {result}, 耗时: {elapsed_time:.6f}s")
        else:
            print("数组过大，跳过测试（避免超时）")
        
        print("-" * 50)

def performance_test():
    """性能测试"""
    print("\n=== 性能测试 ===")
    
    # 测试不同规模的数据
    test_sizes = [8, 10, 12, 15]
    
    for size in test_sizes:
        print(f"\n数组大小: {size}")
        nums = [1] * size
        target = size // 2
        
        solution = Solution()
        start_time = time.time()
        result = solution.findTargetSumWays(nums, target)
        elapsed_time = time.time() - start_time
        
        print(f"回溯算法: 结果={result}, 耗时={elapsed_time:.6f}s")

def verify_examples():
    """验证LeetCode示例"""
    solution = Solution()
    
    print("\n=== 验证LeetCode示例 ===")
    
    # 示例1
    nums1, target1 = [1,1,1,1,1], 3
    result1 = solution.findTargetSumWays(nums1, target1)
    print(f"示例1: nums={nums1}, target={target1}")
    print(f"期望输出: 5, 实际输出: {result1}, {'✓' if result1 == 5 else '✗'}")
    
    # 示例2
    solution2 = Solution()
    nums2, target2 = [1], 1
    result2 = solution2.findTargetSumWays(nums2, target2)
    print(f"示例2: nums={nums2}, target={target2}")
    print(f"期望输出: 1, 实际输出: {result2}, {'✓' if result2 == 1 else '✗'}")
    
    # 小规模测试用例
    solution3 = Solution()
    nums3, target3 = [1, 2, 3], 0
    result3 = solution3.findTargetSumWays(nums3, target3)
    print(f"测试用例3: nums={nums3}, target={target3}")
    print(f"实际输出: {result3}")

if __name__ == "__main__":
    verify_examples()
    test_algorithm()
    performance_test()
